//组合
class Solution {
public:
    vector<int> tmp;
    vector<vector<int>>res;
    vector<vector<int>> combine(int n, int k) 
    {
        dfs(1,n,k);
        return res;
    }
    void dfs(int curi,int n,int k)
    {
        if(tmp.size()==k)
        {
            res.push_back(tmp);
            return;
        }
        for(int i=curi;i<=n;i++)
        {
            tmp.push_back(i);
            dfs(i+1,n,k);
            tmp.pop_back();
        }
    }
};
//组合总和III
class Solution {
public:
    vector<int>tmp;
    vector<vector<int>>res;
    vector<vector<int>> combinationSum3(int k, int n) 
    {
        dfs(k,n,1,0);
        return res;
    }
    void dfs(int k,int n,int curi,int sum)
    {
        if(tmp.size()==k)
        {
            if(sum==n) res.push_back(tmp);
            return;
        }
        for(int i=curi;i<=9;i++)
        {
            tmp.push_back(i);
            dfs(k,n,i+1,sum+i);
            tmp.pop_back();
        }

    }
};

//组合总和
class Solution {
public:
    vector<int>tmp;
    vector<vector<int>>res;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {

        dfs(candidates,target,0,0);
        return res;
    }
    void dfs(vector<int>&candidates,int target,int sum,int curi)
    {
        if(sum>=target)
        {
            if(sum==target) res.push_back(tmp);
            return;
        }
        for(int i=curi;i<candidates.size();i++)
        {
            tmp.push_back(candidates[i]);
            dfs(candidates,target,sum+candidates[i],i);
            tmp.pop_back();
        }
    }
};
//组合总和II
class Solution {
public:
    vector<vector<int>>res;
    vector<int>tmp;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        vector<bool>used(candidates.size(),false);
        sort(candidates.begin(),candidates.end());
        dfs(candidates,used,target,0,0);
        return res;
    }
    void dfs(vector<int>&candidates,vector<bool>& used ,int target,int curi,int sum)
    {
       
        if(sum==target)
        {
            res.push_back(tmp);
            return;
        }
        if(sum>target) return;
        for(int i=curi;i<candidates.size();i++)
        {
            if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false) continue;
            tmp.push_back(candidates[i]);
            used[i]=true;
            dfs(candidates,used,target,i+1,sum+candidates[i]);
            used[i]=false;
            tmp.pop_back();
        }
    }
};